package com.lisp.algorithm.select;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

import com.lisp.algorithm.util.SortUtil;

public class RandomizedSelect {
    
    public static void main(String[] args) {
        int a[] = {1, 8, 2, 7, 3, 2};
        System.out.println(select(a, 3, 0, a.length));
        SortUtil.test(RandomizedSelect::test);
    }
    
    private static void test(int a[]) {
        int copy[] = Arrays.copyOf(a, a.length);
        for(int i=0; i<a.length; i++) {
            int value = select(copy, i+1, 0, copy.length);
            a[i] = value;
        }
    }

    public static int select(int a[], int ith, int start, int end) {
        if(start < end-1) {
            int p = partition(a, start, end);
            int k = p-start+1;
            if(k == ith) {
                return a[p];
            } else if(k < ith) {
                return select(a, ith-k, p+1, end);
            } else {
                return select(a, ith, start, p);
            }
        } else {
            return a[start];
        }
    }
    
    public static int partition(int a[], int start, int end) {
        int x = ThreadLocalRandom.current().nextInt(start, end);
        SortUtil.swap(a, end-1, x);
        
        int pivot = a[end-1];
        int hole = start-1;
        for(int i=start; i<end-1; i++) { // 把小于等于pivot的交换到数组的前面
            if(a[i] <= pivot) {
                hole++;
                SortUtil.swap(a, hole, i);
            }
        }
        SortUtil.swap(a, hole+1, end-1);
        return hole+1;
    }
}
